package com.zdp.leetcodeMiddle;


/*
* 题目描述：
* 给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），
* 并返回该子数组所对应的乘积。
示例 1:
输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
示例 2:
输入: [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-product-subarray
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
* */
public class 乘积最大子数组_152 {
    public static void main(String[] args) {
        乘积最大子数组_152 demo = new 乘积最大子数组_152();
        System.out.println(demo.maxProduct(new int[] {
                2,3,-2,4
        }));
    }

    /*
    * 解题思路： 要找数组中乘积最大 的 连续 子数组
    *  可以参考 题 k次串联后的最大子数组之和
    * 该题不同的是 ： 乘数有正有负，负负得正 有时候会得到一个更大的数
    *  所以 ，单单维护一个最大乘数的数组是不可以的
    * 当 nums[i] 是 负数时，我们希望前面的乘数尽可能小
    *  当 nums[i] 是正数时，我们希望前面的乘数尽可能大
    * 所以维护两个数组 max[i] 和 min[i]
    * max[i] 表示 以i元素结尾的连续子数组的最大乘积
    * min[i] 表示 以i元素结尾的连续子数组的最小乘积
    * max[i] = Math.max(max[i-1]*nums[i],min[i-1]*nums[i],nums[i] )
    * min[i] = Math.min(max[i-1]*nums[i],min[i-1]*nums[i],nums[i] )
    * */
    public int maxProduct(int[] nums) {
        int length = nums.length;
        int[] max = new int[length];
        int[] min = new int[length];
        max[0] = nums[0];
        min[0] = nums[0];
        for(int i =1; i<length;i++){
            max[i] = Math.max(max[i-1]*nums[i],Math.max(min[i-1]*nums[i],nums[i]));
            min[i] = Math.min(max[i-1]*nums[i],Math.min(min[i-1]*nums[i],nums[i]));
        }

        // 取最大值
        int result = Integer.MIN_VALUE;
        for(int i=0;i<length;i++){
            result = Math.max(result,max[i]);
        }
        return result;
    }
}
